package org.chnxi.study.leetcode.questions25.ques22;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * 执行用时 :1 ms, 在所有 Java 提交中击败了97.38%的用户
 * 内存消耗 :40.3 MB, 在所有 Java 提交中击败了5.26%的用户
 */
public class Simple01 {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(1));
        System.out.println(generateParenthesis(2));
        System.out.println(generateParenthesis(3));
    }

    public static List<String> generateParenthesis(int n) {
        //存放结果
        List<String> result = new ArrayList<>();

        //安全性检查
        if(n < 1){
            return result;
        }

        process(result , n , 0 , 0, "" );

        return result;
    }

    /**
     * 使用深度优先算法
     * @param result 存放结果
     * @param len 总生成个数
     * @param left 左边的计数，0开始，生成生成"("
     * @param right 右边计数，0开始，补齐")"
     * @param str 递归过程中传递的单次拼接结果
     */
    private static void process(List<String> result, int len , int left , int right , String str){
        //如果生成字符串长度达到2*len，表示单次生成完成，可加入结果集中
        if(str.length() == len * 2){
            result.add(str);
            return;
        }

        // 优先生成"("
        if(left < len){
            process(result ,len , left+1 , right , str+"(");
        }

        // 补齐剩余的")"
        if(left > right){
            process(result ,len , left , right+1 , str+")");
        }
    }
}
